{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if Point Is Reachable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isReachable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断一个点是否可以到达"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个无穷大的网格图。一开始你在&nbsp;<code>(1, 1)</code>&nbsp;，你需要通过有限步移动到达点&nbsp;<code>(targetX, targetY)</code>&nbsp;。</p>\n",
    "\n",
    "<p><b>每一步</b>&nbsp;，你可以从点&nbsp;<code>(x, y)</code>&nbsp;移动到以下点之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>(x, y - x)</code></li>\n",
    "\t<li><code>(x - y, y)</code></li>\n",
    "\t<li><code>(2 * x, y)</code></li>\n",
    "\t<li><code>(x, 2 * y)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个整数&nbsp;<code>targetX</code> 和&nbsp;<code>targetY</code>&nbsp;，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从&nbsp;<code>(1, 1)</code>&nbsp;出发到达这个点，请你返回<code>true</code> ，否则返回<em>&nbsp;</em><code>false</code><em>&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>targetX = 6, targetY = 9\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>targetX = 4, targetY = 7\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>你可以按照以下路径到达：(1,1) -&gt; (1,2) -&gt; (1,4) -&gt; (1,8) -&gt; (1,7) -&gt; (2,7) -&gt; (4,7) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= targetX, targetY&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-point-is-reachable](https://leetcode.cn/problems/check-if-point-is-reachable/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-point-is-reachable](https://leetcode.cn/problems/check-if-point-is-reachable/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n9', '4\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "    x = self.decrease(targetX)\n",
    "    y = self.decrease(targetY)\n",
    "\n",
    "    while True:\n",
    "      if x == 1 or y == 1:\n",
    "        return True\n",
    "\n",
    "      if x == y:\n",
    "        return False \n",
    "\n",
    "      newCoordinate = self.decrease(x + y)\n",
    "      \n",
    "      if x < y:\n",
    "        y = newCoordinate\n",
    "      else:\n",
    "        x = newCoordinate\n",
    "\n",
    "  def decrease(self, value):\n",
    "    while value % 2 == 0:\n",
    "      value = value >> 1\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:   \n",
    "        factor = gcd(targetX, targetY)\n",
    "        while factor % 2 == 0 and factor != 0:\n",
    "            factor //= 2\n",
    "        return factor == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        return gcd(targetX, targetY) & (gcd(targetX, targetY) - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        while True:\n",
    "            # 规则1\n",
    "            while targetX % 2 == 0: \n",
    "                targetX = targetX // 2\n",
    "            # 规则2\n",
    "            while targetY % 2 == 0: \n",
    "                targetY = targetY // 2\n",
    "\n",
    "            # 跳出while循环条件\n",
    "            if targetY == targetX:\n",
    "                break\n",
    "            # 规则3\n",
    "            else:\n",
    "                if targetX > targetY: \n",
    "                    targetX = int((targetY + targetX) / 2)\n",
    "                else: \n",
    "                    targetY = int((targetY + targetX) / 2)\n",
    "\n",
    "        # 两种结果\n",
    "        if targetX == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g=gcd(targetX,targetY)\n",
    "        return (g&(g-1))==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        # 从(1,1)移动至(x,y)； 移动规则：(x, y-x), (x-y,y), (2*x,y),(x,2*y)\n",
    "        # 判断可达性：\n",
    "        \n",
    "        # 转换为求最大公约数\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return g & (g - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, x: int, y: int) -> bool:\n",
    "        g = gcd(x, y)\n",
    "        return g & (g-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, x: int, y: int) -> bool:\n",
    "        g=gcd(x,y)\n",
    "        return (g&(g-1))==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        if targetX == 1 and targetY == 1:\n",
    "            return True\n",
    "\n",
    "        return bin(gcd(targetX, targetY)).count('1') == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return g & (g - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, x: int, y: int) -> bool:\n",
    "        x = gcd(x,y)\n",
    "        if x & x - 1 == 0:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, tx: int, ty: int) -> bool:\n",
    "        if tx == ty:\n",
    "            while tx % 2 == 0:\n",
    "                tx //= 2\n",
    "           \n",
    "            return tx == 1\n",
    "        while tx != ty:\n",
    "            while tx % 2 == 0:\n",
    "                tx //= 2\n",
    "            while ty % 2 == 0:\n",
    "                ty //= 2\n",
    "            if tx < ty:\n",
    "                ty += tx\n",
    "            elif ty < tx:\n",
    "                tx += ty\n",
    "            \n",
    "            if tx == 1 or ty == 1:\n",
    "                return True\n",
    "        \n",
    "        return tx == 1 and ty == 1\n",
    "                \n",
    "        \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        return math.gcd(targetX, targetY).bit_count() == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = math.gcd(targetX, targetY)\n",
    "        while g % 2 == 0:\n",
    "            g //= 2\n",
    "        return g == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return g & (g - 1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        '''\n",
    "        构造法：\n",
    "        如果两个数中有偶数，将偶数除以2\n",
    "        如果两个数都是奇数，保留较小的数，较大的数加上较小的数\n",
    "        '''\n",
    "        while targetX!=targetY:\n",
    "            if targetX>targetY:\n",
    "                targetX,targetY=targetY,targetX\n",
    "            if targetX%2==1 and targetY%2==1:\n",
    "                targetY+=targetX\n",
    "                continue\n",
    "            if targetX%2==0:\n",
    "                targetX//=2\n",
    "            if targetY%2==0:\n",
    "                targetY//=2\n",
    "        return targetX&(targetX-1)==0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def gcd(x,y):\n",
    "#     return x if y==0 else gcd(y,x%y)\n",
    "class Solution:\n",
    "    def isReachable(self, x: int, y: int) -> bool:\n",
    "        while x and  x % 2==0:\n",
    "            x //= 2\n",
    "        while y and y % 2==0:\n",
    "            y //= 2\n",
    "        print(x,y)\n",
    "        return gcd(x,y) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g = gcd(targetX, targetY)\n",
    "        return (g & (g - 1)) == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isReachable(self, targetX: int, targetY: int) -> bool:\n",
    "        g=gcd(targetX,targetY)\n",
    "        if g&(g-1)==0:return True\n",
    "        else :return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
